1. Field of the Invention
The present invention is directed toward the problem of surface reconstruction, and more particularly toward reconstructing a surface from sample points, a problem arising in many fields including the fields of computer graphics, data visualization, automated cartography, and medical imaging.
2. Art Background
In general, surface reconstruction algorithms approximate an unknown surface from an input that does not explicitly describe that surface. As a first example, in the field of computer graphics, a three-dimensional model may be scanned by a laser range finder to generate sample points that are input to a computer. A surface reconstruction algorithm is then executed to reconstruct a polygonal surface for subsequent manipulation and rendering. As a second example, a scientist studying a dynamical system may reconstruct a surface over a set of data points to ascertain whether the points lie on a smooth surface such as a low-degree polynomial.
Prior art surface reconstruction algorithms fall into two broad categories: those based on triangulation (such as the current invention) and those based on level sets. The most well-known triangulation-based algorithm is the alpha complex construction of Edelsbrunner, et al. at the University of Illinois. (See H. Edelsbrunner and E. Mxc3xccke, xe2x80x9cThree-Dimensional Alpha Shapesxe2x80x9d, ACM Trans. Graphics, 13 (1994) pp. 43-72) Others who have used triangulation-based algorithms include Boissonat (see S. D. Boissonat, xe2x80x9cGeometric Structures for Three-Dimensional Shape Reconstruction,xe2x80x9d ACM Trans. on Graphics 3 (1984) 266-286), Bajaj, et al. at Purdue (see C. L. Bajaj, F. Bernardini, and G. Xu, xe2x80x9cAutomatic Reconstruction of Surfaces and Scaler Fields from 3D Scansxe2x80x9d, Computer Graphics (Proc. SIGGRAPH), 1995, pp. 109-118), and Attali in Prance (See D. Attali R-Regular, xe2x80x9cShape Reconstruction from Unorganized Pointsxe2x80x9d, Proceedings of the ACM Symposium on Computational Geometry, 1997, pp. 248-253). The weakness of the alpha complex is that it assumes a global size parameter, alpha, and hence does not work very well for adaptively sampled surfaces. A more general weakness of all triangulation-based algorithms up until the present invention is spurious holes appearing in the surface where four sample points happen to be cocircular.
Level-set algorithms have been devised by a number of research groups, most notably at the University of Washington (See H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, xe2x80x9cSurface Reconstruction from Unorganized Pointsxe2x80x9d, Computer Graphics (Proc. SIGGRAPH), 1992, pp. 71-78) and at Stanford University. (See B. Curless and M. Levoy, xe2x80x9cA Volumetric Method for Building Complex Models From Range Imagesxe2x80x9d, Computer Graphics (Proc. SIGGRAPH), 1996 and G. Turk and M. Levoy, xe2x80x9cZippered Polygon Meshes from Range Imagesxe2x80x9d, Computer Graphics (Proc. SIGGRAPH), 1994, pp. 311-318) Level-set algorithms work quite well in practice, and are currently preferred over triangulation-based methods for inexact applications such as computer graphics. Two characteristics of level-set algorithms become liabilities for more exact applications such as scientific visualization: first, level-set algorithms approximate (pass nearby) rather than interpolate (pass through) the sample points; and second, level-set algorithms strongly prefer closed surfaces over surfaces with boundaries.
The surface reconstruction algorithm of the present invention is triangulation-based with provably reliable performance for both inexact and exact applications. Unlike other triangulation-based algorithms, the present invention assumes no global size parameter and avoids spurious holes. Unlike level-set algorithms, the invention gives a polygonal surface whose vertex set is exactly the set of sample points, and the invention will leave a boundary, for example a xe2x80x9cwindowxe2x80x9d into the surface, when the polygons that would fill in the boundary are not adequately supported by the data.
The surface reconstruction algorithm generates a d-dimensional surface from a set of sample points. In the typical case, the surface reconstruction algorithm reconstructs a two-dimensional surface embedded in three-dimensional space from the set of sample points. The surface reconstruction algorithm first generates the Voronoi diagram of the sample points. The Voronoi diagram represents a division of space into Voronoi cells, one Voronoi cell for each sample point, such that each sample point""s Voronoi cell consists of that part of space closer to it than to any other sample point. The surface reconstruction system uses the sample points and the shapes of their Voronoi cells to determine which surface elements (triangles in the case of a two-dimensional surface in three dimensions) to include in the reconstructed surface. In one embodiment, Voronoi cell shape information includes locations of vertices, angles at vertices and edges, aspect ratio of the cell, and directions and lengths of principal axes of the cell.
For the two-dimensional surface in three dimensions embodiment, the Voronoi cell shape information is the location of one or two specially selected vertices, called xe2x80x9cpolesxe2x80x9d, from each Voronoi cell. The first pole, p+, of sample point v, is the vertex of v""s Voronoi cell farthest from v. If v lies on the convex hull of the sample points, then its Voronoi cell is unbounded, and p+ is any point so that vector vp+ points in a direction in which the Voronoi cell is unbounded. In either case, the second pole pxe2x88x92 is the vertex of v""s Voronoi cell farthest from v such that vpxe2x88x92 has negative dot product with vp+.
After the selection of poles, the surface reconstruction algorithm computes the Delaunay triangulation of the sample points and the poles and retains only those triangles in which all three vertices are sample points. In two last optional steps, the algorithm performs some further triangle filtering. Triangles may be removed based on the angle between the vector to the pole at a vertex and the normal to the triangle. Finally the algorithm extracts a two-dimensional manifold from the set of retained triangles. This manifold extraction step removes each triangle with a sharp dihedral (for example, an edge not adjacent to another triangle), and then takes the inside or outside of the union of triangles.